package cn.lishiyuan.leetcode;

import java.util.*;

/**
 * 基础01背包问题：
 *
 * 有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
 */
public class KnapsackProblem01 {

    /**
     * 回溯法处理
     */
    public static List<Integer> resolve(int[] weight, int[] value, int capacity ){
        return resolve(weight,value,capacity,0,0);
    }


    private static List<Integer> resolve(int[] weight,int[] value,int capacity,int start,int pValue){
        if(capacity <= 0 || start >= weight.length){
            // 没有容量了或者已经是最后一件物品了
            return Collections.emptyList();
        }

        List<Integer> select = new ArrayList<>();
        int maxValue = Integer.MIN_VALUE;

        // 重量没超出限制
        for(int i = start; i < weight.length; i++){
            // 当前物品小于剩余容量
            if(weight[i] <= capacity){
                // 尝试放入
                // 放入下一个
                List<Integer> list =  resolve(weight,value,capacity-weight[i],i+1,pValue+value[i]);
                // 计算总价值
                int v = list.stream().mapToInt(data -> value[data]).sum();
                v += value[i];

                //装入后价值较高则选择这个价值高的
                if(v > maxValue){
                    // 始终放入价值最大的
                    maxValue = v;
                    // 清除旧的
                    select.clear();
                    // 放入
                    select.add(i);
                    select.addAll(list);
                }
            }
        }
        return select;
    }


    /**
     * 动态规划处理
     * @param weight
     * @param value
     * @param capacity
     * @return
     */
    public static List<Integer> resolveDP(int[] weight, int[] value, int capacity){
        // 状态转移，每次转移的状态有容量变化 与 物品选择与否 和 物品总价值
        Map<Integer, Map<Integer,Integer>> map = new HashMap<>();

        // 初始化
        for(int i = 0; i < weight.length; i++){
            // 不放入的情况下价值为0
            Map<Integer, Integer> v = new HashMap<>();
            v.put(0, 0);
            map.put(i, v);
        }

        // 第一件物品放入的的情况下，其价值
        if(weight[0] <= capacity){
            map.get(0).put(weight[0], value[0]);
        }

        for(int i = 1; i < weight.length; i++){
            // 当前物品只有放入和不放入两种选择，而其状态只能由上个状态过来

            // 当前状态
            Map<Integer, Integer> v = map.get(i);
            Map<Integer, Integer> prev = map.get(i - 1);
            for(Map.Entry<Integer, Integer> entry : prev.entrySet()){
                // 上个加上这个是否已经超出了限制，如果没有则放入
                Integer oldKey = entry.getKey();
                Integer key = oldKey + weight[i];
                if(key <= capacity){
                    // 此时可能存在两种情况
                    // 一是前面的的状态可能有相同的重量的价值
                    Integer old = prev.getOrDefault(key,0);

                    // 二是当前重量的重价值
                    int newValue = entry.getValue() + value[i];

                    // 放入较大的一个
                    v.put(key, Math.max(old,newValue));
                }else {
                    // 不能放入，就是上个重量的价值
                    v.put(oldKey, entry.getValue());
                }
            }
        }

        // 由于状态是一步步转移下来的最后的重量里面选择价值最高的就是结果
        Map<Integer, Integer> v = map.get(weight.length - 1);
        // 取价值最大的
        int maxValue = Integer.MIN_VALUE;
        Map.Entry<Integer, Integer> select =null;
        for (Map.Entry<Integer, Integer> entry : v.entrySet()) {
            if (entry.getValue() > maxValue) {
                maxValue = entry.getValue();
                select = entry;
            }
        }

        // 逆向恢复选择的物品
        List<Integer> selectList = new ArrayList<>();

        if (select != null){
            int nowWeight = select.getKey();
            int nowValue = select.getValue();
            for (int i = weight.length - 1 ; i >= 0; i--) {
                // 上个状态
                Integer val = map.getOrDefault(i-1,Collections.emptyMap()).get(nowWeight);
                // 三种情况，不存在或者小于价值小i与当前价值的时候，那么当前物品肯定被选择了
                if (val==null || val < nowValue){
                    // 物品被选择了
                    selectList.add(i);
                    // 去掉物品的重量与价值
                    nowWeight -= weight[i];
                    nowValue -= value[i];
                }
            }
        }

        return selectList;
    }
}
